The present invention relates to systems for storing data and generating parity data to allow reconstruction of lost data, and in particular to systems using arrays of disk drives.
Redundant Arrays of Inexpensive Disks (RAID) is a relatively new technology for increasing the reliability and performance of disk storage systems. RAID increases the performance of disk subsystems by using many small, inexpensive disk drives in tandem. RAID increases the reliability of disk subsystems by storing redundant data on one or more of the disk drives in the system. In the event of a disk failure, the redundant data can be used to reconstruct the data on the failed drive.
One method for generating redundant data is block parity. Block parity is the exclusive-or operation of two or more blocks of data. If one block of data is lost, it can be recreated by the bit-wise exclusive-or operation of the remaining data blocks and the parity block.
One method for implementing RAID (RAID 5) spreads parity blocks across all the disks in the array. An array can be viewed as a series of rows and columns. The individual disks are the columns and the rows make up the blocks. Blocks are made up of one or more physical disk sectors (which are typically 512 bytes in size). Each row has data blocks and a single parity block. FIG. 1 shows the parity blocks spread across the columns in a Left-Symmetrical format.
The parity block for any row in the array is generated by the exclusive-or of all the data blocks in the row. If, for example, column (disk) 2 fails, Rows 0, 2, and 3 lose data blocks and Row 1 loses its parity block. For Row 1, no data is lost but the parity block can no longer be updated. For Rows 0, 2, and 3, access to the data blocks in the failed column requires the data to be reconstructed for the failed data block. This can be done by reading the other data blocks and parity block in the row and performing an exclusive-or. The result of the operation is the data for the failed data block.
There are several different ways block parity is generated and accessed in RAID systems. A common operation that involves block parity is known as Read-Modify-Write. The Read-Modify-Write method is used when a single block of data for the row is being written. Typically, the block parity for RAID systems is generated using a general purpose Central Processing Unit (CPU) 12 and Random Access Memory (RAM) 14, as shown in FIGS. 2A-2C. FIGS. 2A-2C show how a Read-Modify-Write operation is implemented with a general purpose CPU and RAM.
The Read-Modify-Write operation updates the new data block being written and the parity block for the row. To generate the new parity block requires reading the old data block and the old parity block from the array and exclusive-or'ing the new data block, the old data block, and the old parity block.